// https://leetcode.cn/problems/word-search/description/

// 算法思路总结：
// 1. 深度优先搜索在二维网格中查找单词
// 2. 从每个格子开始尝试匹配单词路径
// 3. 使用vis数组记录访问状态，避免重复使用同一格子
// 4. 四方向扩展搜索，匹配成功立即返回
// 5. 先检查字符匹配，再判断是否完成单词搜索
// 6. 时间复杂度：O(m×n×4^L)，空间复杂度：O(L)

#include <iostream>
using namespace std;

#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    int m, n;
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    bool vis[7][7];
    
    bool exist(vector<vector<char>>& board, string word) 
    {
        memset(vis, 0, sizeof(vis));
        m = board.size(), n = board[0].size();

        for (int i = 0 ; i < m ; i++)                
        {                                                         
            for (int j = 0 ; j < n ; j++)               
            {
                if (dfs(board, i, j, word, 0) == true)
                    return true;
            }
        }

        return false;
    }

    bool dfs(vector<vector<char>>& board, int a, int b, string& word, int pos)
    {
        if (board[a][b] != word[pos]) return false;
        if (pos == word.size() - 1) return true;
        
        vis[a][b] = true;
        for (int i = 0 ; i < 4 ; i++)
        {
            int x = a + dx[i], y = b + dy[i];
            if (x >= 0 && y >= 0 && x < m && y < n && vis[x][y] == false)
            {
                if (dfs(board, x, y, word, pos + 1) == true)
                    return true;
            }
        }
        vis[a][b] = false;

        return false;
    }
};

int main()
{
    vector<vector<char>> board1 = {
        {'A','B','C','E'},
        {'S','F','C','S'},
        {'A','D','E','E'}
    };
    string word1 = "ABCCED";
    
    vector<vector<char>> board2 = {
        {'A','B','C','E'},
        {'S','F','C','S'},
        {'A','D','E','E'}
    };
    string word2 = "SEE";

    Solution sol;

    cout << sol.exist(board1, word1) << endl;
    cout << sol.exist(board2, word2) << endl;

    return 0;
}